///*
//EP3D is a real-time 3D planet engine , which in addition to providing 
//substandard scene rendering and scene management, of course, it also 
//provides some basic class libraries to build the entire virtual 
//planet, or even the entire universe.
//
//Copyright (C) 2010  Hongjiang Zhang	(zhjwyat@gmail.com)
//
//This program is free software: you can redistribute it and/or modify
//it under the terms of the GNU General Public License as published by
//the Free Software Foundation, either version 3 of the License, or
//(at your option) any later version.
//
//This program is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU General Public License for more details.
//
//You should have received a copy of the GNU General Public License
//along with this program.  If not, see <http://www.gnu.org/licenses/>.
//*/
//
//#ifndef EP3D_QUADNODE_H
//#define EP3D_QUADNODE_H
//#include "EP3DSceneNode.h"
//#include "EP3DVector2.h"
//
//namespace EP3D
//{
//	class QuadMap;
//	class EP3DEXPORT QuadNode
//		:public SceneNode
//	{
//		DeclareRtti;
//	public:
//		enum
//		{
//			TOP_LEFT = 0,
//			TOP_RIGHT = 1,
//			BOTTOM_LFET = 2,
//			BOTTOM_RIGHT = 3
//		};
//
//		enum
//		{
//			TOP_EDGE = 0,
//			RIGHT_EDGE = 1,
//			BOTTOM_EDGE = 2,
//			LEFT_EDGE = 3
//		};
//
//		enum 
//		{
//			FACE_MASK = 0x0007,
//			QUADRANT_MASK = 0x0018,
//			LEVEL_MASK = 0x03E0,
//			CAMERA_IN_MASK = 0x0C00,
//			NODE_DIRTY = 0x1000,
//
//			BEYOND_HORIZON_MASK = 0x000F0000,
//			OUTSIDE_FRUSTUM_MASK = 0x00F00000
//		};
//
//		QuadNode(QuadNode* pkParent, QuadMap* pkMap, int nQuadrant);
//		virtual ~QuadNode(void);
//
//		int GetQuadrant() { return m_nNodeFlags & QUADRANT_MASK; }
//		int GetLevel() { return (m_nNodeFlags & LEVEL_MASK) >> 3; }
//		bool IdDirty() { return (m_nNodeFlags & NODE_DIRTY) >> 5; }
//		bool IsCameraIn(int n) { return (m_nNodeFlags & (1 << (10 + n))) != 0; }
//		bool IsBeyondHorizon(int n) { return (m_nNodeFlags & (1 << (16 + n))) != 0; }
//		bool IsOutsideFrustum(int n) { return (m_nNodeFlags & (1 << (20 + n))) != 0; }
//
//		f32 GetMinX() { return m_kBBox.GetMin().x; }
//		f32 GetMinY() { return m_kBBox.GetMin().y; }
//		f32 GetMaxX() { return m_kBBox.GetMax().x; }
//		f32 GetMaxY() { return m_kBBox.GetMax().y; }
//		f32 GetMidX() { return (GetMinX() + GetMaxX()) * 0.5f; }
//		f32 GetMidY() { return (GetMinY() + GetMaxY()) * 0.5f; }
//		f32 GetWidth() { return GetMaxX() - GetMinX(); }
//		f32 GetHeight() { return GetMaxY() - GetMinY(); }
//
//		bool IsLeaf() { return m_pkChild[0] == NULL && m_pkChild[1] == NULL && m_pkChild[2] == NULL && m_pkChild[3] == NULL; }
//		bool AffectsNode(f32 x, f32 y, f32 fRadius);
//		bool HitTest(f32 x, f32 y, uchar nQuadrant = -1);
//		bool GetHeight(f32 x, f32 y);
//		f32 GetHeightFromMap(const Vector2f& pos);
//
//		QuadNode* FindQuadrantNeighbor(int Quadrant, int nEdge, bool bForceSplit = false)
//		{
//			QuadNode* pkNeighbor = NULL;
//			switch (Quadrant)
//			{
//			case TOP_LEFT:
//				switch (nEdge)
//				{
//				case TOP_EDGE:
//					if (m_pkNeighbor[nEdge]) {
//						if (bForceSplit) {
//							m_pkNeighbor[nEdge]->Split(BOTTOM_LFET);
//						}
//						pkNeighbor = m_pkNeighbor[nEdge]->m_pkChild[BOTTOM_LFET];
//					}
//					break;
//				case RIGHT_EDGE:
//					pkNeighbor = m_pkChild[TOP_RIGHT];
//					break;
//				case BOTTOM_EDGE:
//					pkNeighbor = m_pkChild[BOTTOM_LFET];
//					break;
//				case LEFT_EDGE:
//					if (m_pkNeighbor[nEdge]) {
//						if (bForceSplit) {
//							m_pkNeighbor[nEdge]->Split(TOP_RIGHT);
//						}
//						pkNeighbor = m_pkNeighbor[nEdge]->m_pkChild[TOP_RIGHT];
//					}
//					break;
//				}
//				break;
//			case TOP_RIGHT:
//				switch (nEdge)
//				{
//				case TOP_EDGE:
//					if (m_pkNeighbor[nEdge]) {
//						if (bForceSplit) {
//							m_pkNeighbor[nEdge]->Split(BOTTOM_RIGHT);
//						}
//						pkNeighbor = m_pkNeighbor[nEdge]->m_pkChild[BOTTOM_RIGHT];
//					}
//					break;
//				case RIGHT_EDGE:
//					if (m_pkNeighbor[nEdge]) {
//						if (bForceSplit) {
//							m_pkNeighbor[nEdge]->Split(TOP_LEFT);
//						}
//						pkNeighbor = m_pkNeighbor[nEdge]->m_pkChild[TOP_LEFT];
//					}
//					break;
//				case BOTTOM_EDGE:
//					pkNeighbor = m_pkChild[BOTTOM_RIGHT];
//					break;
//				case LEFT_EDGE:
//					pkNeighbor = m_pkChild[TOP_LEFT];
//					break;
//				}
//				break;
//			case BOTTOM_LFET:
//				switch (nEdge)
//				{
//				case TOP_EDGE:
//					pkNeighbor = m_pkChild[TOP_LEFT];
//					break;
//				case RIGHT_EDGE:
//					pkNeighbor = m_pkChild[BOTTOM_RIGHT];
//					break;
//				case BOTTOM_EDGE:
//					if (m_pkNeighbor[nEdge]) {
//						if (bForceSplit) {
//							m_pkNeighbor[nEdge]->Split(TOP_LEFT);
//						}
//						pkNeighbor = m_pkNeighbor[nEdge]->m_pkChild[TOP_LEFT];
//					}
//					break;
//				case LEFT_EDGE:
//					if (m_pkNeighbor[nEdge]) {
//						if (bForceSplit) {
//							m_pkNeighbor[nEdge]->Split(BOTTOM_RIGHT);
//						}
//						pkNeighbor = m_pkNeighbor[nEdge]->m_pkChild[BOTTOM_RIGHT];
//					}
//					break;
//				}
//				break;
//			case BOTTOM_RIGHT:
//				switch (nEdge)
//				{
//				case TOP_EDGE:
//					pkNeighbor = m_pkChild[TOP_RIGHT];
//					break;
//				case RIGHT_EDGE:
//					if (m_pkNeighbor[nEdge]) {
//						if (bForceSplit) {
//							m_pkNeighbor[nEdge]->Split(BOTTOM_LFET);
//						}
//						pkNeighbor = m_pkNeighbor[nEdge]->m_pkChild[BOTTOM_LFET];
//					}
//					break;
//				case BOTTOM_EDGE:
//					if (m_pkNeighbor[nEdge]) {
//						if (bForceSplit) {
//							m_pkNeighbor[nEdge]->Split(TOP_RIGHT);
//						}
//						pkNeighbor = m_pkNeighbor[nEdge]->m_pkChild[TOP_RIGHT];
//					}
//					break;
//				case LEFT_EDGE:
//					pkNeighbor = m_pkChild[BOTTOM_LFET];
//					break;
//				}
//				break;
//			}
//			return pkNeighbor;
//		}
//		QuadNode* FindNeighbor(int nEdge, bool bForceSplit = false)
//		{
//			if (!m_pkParent) {
//				return m_pkNeighbor[nEdge];
//			}
//			return m_pkParent->FindQuadrantNeighbor(GetQuadrant(), nEdge, bForceSplit);
//		}
//		void UpdateNeighbors()
//		{
//			for (int i = 0; i < 4; ++i) {
//				m_pkNeighbor[i] = FindNeighbor(i);
//			}
//		}
//		int FindMatchingEdge(int nEdge)
//		{
//			for (int i = 0; i < 4; ++i) {
//				if (m_pkNeighbor[nEdge] && m_pkNeighbor[nEdge]->m_pkNeighbor[i] == this) {
//					return i;
//				}
//			}
//			return -1;
//		}
//
//		void Split(int nQuadrant)
//		{
//			if (m_pkChild[nQuadrant]) {
//				return;
//			}
//
//			switch (nQuadrant)
//			{
//			case TOP_LEFT:
//				if (!FindNeighbor(TOP_EDGE, true) || !FindNeighbor(LEFT_EDGE, true)) {
//					return;
//				}
//				break;
//			case TOP_RIGHT:
//				if (!FindNeighbor(TOP_EDGE, true) || !FindNeighbor(RIGHT_EDGE, true)) {
//					return;
//				}
//				break;
//			case BOTTOM_LFET:
//				if (!FindNeighbor(BOTTOM_EDGE, true) || !FindNeighbor(LEFT_EDGE, true)) {
//					return;
//				}
//				break;
//			case BOTTOM_RIGHT:
//				if (!FindNeighbor(BOTTOM_EDGE, true) || !FindNeighbor(RIGHT_EDGE, true)) {
//					return;
//				}
//				break;
//			}
//
//			if (m_pkMap->CanSplit()) {
//				m_pkChild[nQuadrant] = EP3DNew QuadNode(this, m_pkMap, nQuadrant);
//			}
//		}
//
//		bool CanMerge()
//		{
//			if (!IsLeaf()) {
//				return false;
//			}
//
//			if (m_pkNeighbor[TOP_EDGE] && (FindQuadrantNeighbor(TOP_LEFT, TOP_EDGE) || FindQuadrantNeighbor(TOP_RIGHT, TOP_EDGE))) {
//				return false;
//			}
//			if (m_pkNeighbor[RIGHT_EDGE] && (FindQuadrantNeighbor(TOP_RIGHT, TOP_EDGE) || FindQuadrantNeighbor(BOTTOM_RIGHT, TOP_EDGE))) {
//				return false;
//			}
//			if (m_pkNeighbor[BOTTOM_EDGE] && (FindQuadrantNeighbor(BOTTOM_RIGHT, BOTTOM_EDGE) || FindQuadrantNeighbor(BOTTOM_LFET, BOTTOM_EDGE))) {
//				return false;
//			}
//			if (m_pkNeighbor[LEFT_EDGE] && (FindQuadrantNeighbor(BOTTOM_LFET, LEFT_EDGE) || FindQuadrantNeighbor(TOP_LEFT, LEFT_EDGE))) {
//				return false;
//			}
//
//			return true;
//		}
//
//		bool Merge(int nQuadrant)
//		{
//			QuadNode* pkNode = m_pkChild[nQuadrant];
//			if (!pkNode) {
//				return true;
//			}
//
//			bool bSuccess = true;
//			if (!pkNode->Merge(0)) {
//				bSuccess = false;
//			}
//			if (!pkNode->Merge(1)) {
//				bSuccess = false;
//			}
//			if (!pkNode->Merge(2)) {
//				bSuccess = false;
//			}
//			if (!pkNode->Merge(3)) {
//				bSuccess = false;
//			}
//			if (!bSuccess || !pkNode->CanMerge()) {
//				return false;
//			}
//
//			EP3DDelete m_pkChild[nQuadrant];
//			return true;
//		}
//
//		virtual void Update(uint elapsedMs)
//		{
//			Vector3f vCamera = m_pkMgr->GetActiveCamera()->GetAbsolutePosition();
//			m_nNodeFlags &= ~(CAMERA_IN_MASK | BEYOND_HORIZON_MASK | OUTSIDE_FRUSTUM_MASK);
//			
//			f32 fMid[2] = {Mathf::Avg(GetMinX(), GetMaxX()), Mathf::Avg(GetMinY(), GetMaxY())};
//			f32 x[2] = {Mathf::Avg(GetMidX(), GetMidX()), Mathf::Avg(GetMidX(), GetMaxX())};
//			f32 y[2] = {Mathf::Avg(GetMinY(), GetMidY()), Mathf::Avg(GetMidY(), GetMaxY())};
//			f32 z = m_kBBox.GetCenter().z;
//
//			Vector3f vQuadrant[4] = 
//			{
//				Vector3f(x[0], y[0], z),
//				Vector3f(x[1], y[0], z),
//				Vector3f(x[0], y[1], z),
//				Vector3f(x[1], y[1], z),
//			};
//
//			f32 fDistance[4] =
//			{
//				vCamera.Distance(vQuadrant[0]),
//				vCamera.Distance(vQuadrant[1]),
//				vCamera.Distance(vQuadrant[2]),
//				vCamera.Distance(vQuadrant[3]),
//			};
//
//			if (vCamera.x < fMid[0]) {
//				if (vCamera.y < fMid[1]) {
//					m_nSort[0] = 0;
//					m_nSort[1] = 1;
//					m_nSort[2] = 2;
//					m_nSort[3] = 3;
//				}
//				else {
//					m_nSort[0] = 2;
//					m_nSort[1] = 0;
//					m_nSort[2] = 3;
//					m_nSort[3] = 1;
//
//				}
//			}
//			else {
//				if (vCamera.y < fMid[1]) {
//					m_nSort[0] = 1;
//					m_nSort[1] = 0;
//					m_nSort[2] = 3;
//					m_nSort[3] = 2;
//				}
//				else {
//					m_nSort[0] = 3;
//					m_nSort[1] = 1;
//					m_nSort[2] = 2;
//					m_nSort[3] = 0;
//				}
//			}
//
//// 			for (int i = 0; i < 4; ++i) {
//// 				int nQuadrant = m_nSort[i];
//// 
//// 				if (HitTest(vCamera.x, vCamera.y, nQuadrant)) {
//// 					m_nNodeFlags |= (nQuadrant << 10) & CAMERA_IN_MASK; 
//// 				}
//// 				else {
//// 			}
//
//
//			SceneNode::Update(elapsedMs);
//		}
//	protected:
//		QuadNode* m_pkParent;
//		QuadNode* m_pkChild[4];
//		QuadNode* GetParent() { return m_pkParent; }
//		void SetParent(QuadNode* pkParent) { m_pkParent = pkParent; }
//		QuadNode* GetChild(int n) { return m_pkChild[n]; }
//		void SetChild(int n, QuadNode* pkChild) { m_pkChild[n] = pkChild; }
//
//		uint m_nNodeFlags;
//		QuadMap* m_pkMap;
//		QuadNode* m_pkNeighbor[4];
//		uchar m_nSort[4];
//		BBox3f m_kBBox;
//	};
//}
//#endif
//
//
